UVa/10298 - Power Strings/10298.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int MAXN = 1000005;
  28
  29 int f[MAXN];
  30
  31 void precomputePrefixFunction(char s[], int n) {
  32     f[0] = -1;
  33     for (int i = 1; i < n; ++i) {
  34         f[i] = f[i-1];
  35         while (f[i] > -1 and s[f[i]+1] != s[i]) {
  36             f[i] = f[f[i]];
  37         }
  38         if (s[f[i]+1] == s[i]) {
  39             f[i]++;
  40         }
  41     }
  42 }
  43
  44 char s[MAXN];
  45
  46 int main(){
  47     // s = " abcabcabcabc";
  48     // precomputePrefixFunction(s);
  49     // for (int i = 1; i < s.length(); ++i) {
  50     //     printf("%d ", f[i]);
  51     // }
  52     // puts("");
  53
  54     while (true) {
  55         gets(s);
  56         int n = strlen(s);
  57         if (n == 1 and s[0] == '.') break;
  58         assert(n > 0);
  59         if (n <= 1) {
  60             printf("%d\n", n);
  61             continue;
  62         }
  63         precomputePrefixFunction(s, n);
  64
  65         //printf("s = %s\n", s); for (int i = 0; i < s; ++i) { printf("%d ", f[i]); } puts("");
  66
  67         int j = n - 1;
  68         assert(j >= 0);
  69         while (j - 1 >= 0 and f[j-1] + 1 == f[j] and f[j] > 0) j--;
  70
  71         int periodSize = j;
  72         if (f[j] != 0) periodSize = n;
  73         if ((n % periodSize) != 0) periodSize = n;
  74         //printf("periodSize is %d\n", periodSize);
  75         assert((n % periodSize) == 0);
  76         printf("%d\n", n / periodSize);
  77     }
  78     return 0;
  79 }